#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0014.py
@time: 2021/9/14 13:55
@desc:
'''
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> list:
        if not root:
            return []

        res, queue = [], []
        queue.append(root)
        flag = 1
        while len(queue)>0:
            tmp = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                tmp.append(node.val)
                if not node.left==None:
                    queue.append(node.left)
                if not node.right==None:
                    queue.append(node.right)
            res.append(tmp[::flag])
            flag *= -1
        return res

def buildTree()->TreeNode:
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)

    return root

if __name__ == '__main__':
    inp = buildTree()
    s = Solution()
    res = s.levelOrder(inp)
    print(res)